package com.peng.leetcode.tree;

/**
 * RecoverTree
 * 99. 恢复二叉搜索树
 * https://leetcode.cn/problems/recover-binary-search-tree/
 * <p>
 * Created on 2022/12/6
 *
 * @author lupeng
 */
public class RecoverTree {
    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root);
        if (x != null && y != null) {
            swap(x, y);
        }

    }

    TreeNode x = null;
    TreeNode y = null;
    TreeNode pre = null;

    void dfs(TreeNode n) {
        if (n == null) {
            return;
        }
        dfs(n.left);
        if (pre != null && pre.val > n.val) {
            y = n;
            if (x == null) {
                x = pre;
            }
        }
        pre = n;
        dfs(n.right);
    }


    void swap(TreeNode n1, TreeNode n2) {
        int temp = n1.val;
        n1.val = n2.val;
        n2.val = temp;
    }
}
